/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/**
 * @author zhong
 *
 */
public class ContainVirus {
	int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

	class Node {

		int x, y;

		Node parent;
		ArrayList<Node> son = new ArrayList<>();;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
			this.parent = this;
		}

		public void union(Node other, Set<Node> roots) {
			Node root1 = this.getroot();
			Node root2 = other.getroot();
			if (root1 != root2) {// 如果不是同一个并查集里面的，则合并
				root2.parent = root1;
				root1.son.add(root2);
				roots.remove(root2);
				roots.add(root1);
			}
		}

		public Node getroot() {
			Node node = this;
			while (node.parent != node) {
				node = node.parent;
			}
			return node;
		}

		@Override
		public boolean equals(Object arg0) {
			Node other = (Node) arg0;
			return this.x == other.x && this.y == other.y;
		}

		@Override
		public int hashCode() {
			return (this.toString()).hashCode();
		}

		@Override
		public String toString() {
			return x + "," + y;
		}
	}

	public int containVirus(int[][] grid) {
		int n = grid.length;
		int m = grid[0].length;

		Map<String, Node> nodes = new HashMap<>();// 所有已经污染的
		Set<Node> roots = new HashSet<>();// 所有污染的区域，用一个坐标表示,及其将会污染的个数

		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < m; j++) {
				if (grid[i][j] == 1) {
					Node node = new Node(i, j);
					String lString = i + "," + (j - 1);
					String uString = (i - 1) + "," + j;
					Node lNode = nodes.get(lString);
					Node uNode = nodes.get(uString);
					nodes.put(i + "," + j, node);
					if (lNode != null && uNode != null) {
						lNode.union(uNode, roots);
						lNode.union(node, roots);
					} else if (lNode != null) {
						lNode.union(node, roots);
					} else if (uNode != null) {
						uNode.union(node, roots);
					} else {
						roots.add(node);
					}
					// System.out.println(node + " " + roots.size());
				}
			}
		}
		Set<String> walls = new HashSet<>();

		System.out.println(roots.size());
		System.out.println(roots);
		while (true) {
			Map<String, ArrayList<Node>> threantenNodes = new HashMap<>();// 所有被威胁的点及威胁它们的并查集的根
			Node maxRoot = null;
			int maxCount = 0;
			for (Node node : roots) {
				// 每个root
				int count = threat(node, grid, walls, threantenNodes);// 这个点开始的能够威胁多少个,并且把它们标记为 -1
				if (count > maxCount) {
					maxRoot = node;
					maxCount = count;
				}
				System.out.println(node.toString() + ":" + count);
			}

			if (maxCount == 0) {// 没有可以污染的区域了，则跳出循环
				break;
			}
			// 把最大威胁的并查集附近建立墙
			threat(maxRoot, grid, walls, null);
			System.out.println(walls.size());
			// 移除掉建立了墙的set
			roots.remove(maxRoot);
			// 把被污染的变为1且union到附近的点
			for (String string : threantenNodes.keySet()) {
				ArrayList<Node> list = threantenNodes.get(string);
				list.remove(maxRoot);
				if (list.isEmpty()) {
					continue;
				}
				String[] strings = string.split(",");
				int i1 = Integer.parseInt(strings[0]);
				int i2 = Integer.parseInt(strings[1]);
				// 把被威胁的点加入该并查集
				grid[i1][i2] = 1;
				Node node = new Node(i1, i2);
				nodes.put(node.toString(), node);
				// 对周围已经为1的进行合并-----而不是对威胁来源进行合并。因为有可能两个新的1链接在一起，也需要合并
				ArrayList<Node> neibors = new ArrayList<>(4);
				for (int[] js : dir) {
					int x = i1 + js[0];
					int y = i2 + js[1];
					if (x < n && x > -1 && y < m && y > -1 && grid[x][y] == 1 && !walls.contains(strOf(x, y, i1, i2))) {
						neibors.add(nodes.get(x + "," + y));
					}
				}
				Node root1 = neibors.get(0).getroot();// 是否可能出现周围都不是1 的情况？？？
				root1.union(node, roots);
				// 如果一个点被多个区域威胁，则这些区域可以合并
				for (int i = 1; i < neibors.size(); i++) {// --------------1.注意要加入新的根，因为neibors.get(0)的根可能是新的1，即原来没有的根----2.注意要先删除后者的root，然后再合并，否则会删除合并后的根，这是错误的
					root1.union(neibors.get(i), roots);
				}
			}
		}
		return walls.size();
	}

	private String strOf(int x, int y, int i1, int i2) {
		String string = x + "," + y;
		if (i1 < x || (i1 == x && i2 < y)) {
			return i1 + "," + i2 + "#" + string;
		} else {
			return (string + "#" + i1 + "," + i2);
		}
	}

	private int threat(Node node, int[][] grid, Set<String> walls, Map<String, ArrayList<Node>> threantenNodes) {
		int n = grid.length, m = grid[0].length;
		int count = 0;
		boolean visited[][] = new boolean[n][m];
		Queue<Node> queue = new LinkedList<>();
		queue.add(node);
		visited[node.x][node.y] = true;
		while (!queue.isEmpty()) {
			Node node2 = queue.poll();
			// 把所有周围为0的加入threantenNodes
			int i1 = node2.x;
			int i2 = node2.y;
			for (int[] js : dir) {
				int x = i1 + js[0];
				int y = i2 + js[1];
				if (x < n && x > -1 && y < m && y > -1 && grid[x][y] == 0) {
					String string = x + "," + y;
					if (threantenNodes == null) {// 是来建立墙
						walls.add(strOf(x, y, i1, i2));
					} else if (!visited[x][y] && !walls.contains(strOf(x, y, i1, i2))) {// 是来统计将要被污染的个数,没有墙且原来是0的会被污染
						visited[x][y] = true;
						if (!threantenNodes.containsKey(string)) {
							threantenNodes.put(string, new ArrayList<>());
						}
						count++;
						threantenNodes.get(string).add(node);
					}
				}
			}
			for (Node neib : node2.son) {
				if (!visited[neib.x][neib.y]) {
					visited[neib.x][neib.y] = true;
					queue.add(neib);
				}
			}
		}
		return count;
	}

	/**
	 * 计算连续的值为1造成的 -1的值（将被污染的区域）的个数，并且标记为指定的负数来标识不同的区域
	 * 
	 * @param visited
	 * @param grid
	 * @param i
	 * @param j
	 * @return
	 */
	private int getCount(boolean[][] visited, int[][] grid, int i, int j) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(i);
		queue.add(j);
		visited[i][j] = true;
		int count = 0;
		int n = visited.length;
		int m = visited[0].length;
		while (!queue.isEmpty()) {
			int i1 = queue.poll();
			int i2 = queue.poll();
			// 对于周围每个没有访问过的值1（连续污染）的，加入queue
			for (int[] js : dir) {
				int x = i1 + js[0];
				int y = i2 + js[1];
				if (x >= 0 && x < n && y >= 0 && y < m) {
					if (!visited[x][y] && grid[x][y] == 1) {
						queue.add(x);
						queue.add(y);
						visited[x][y] = true;
					} else if (grid[x][y] == -1) {// 由于它造成的待污染cell——同一个cell可能被两个不连续的污染源造成
						// 计算并标记周围的待污染区域个数
						count++;
					}
				}
			}
		}
		return count;
	}

	/**
	 * 把后者合并到前者里面，即后者的root的parent是前者的root
	 * 
	 * @param unionSet
	 * @param string
	 * @param string2
	 */
	private void union(Map<String, String> unionSet, String string, String string2) {
		String root1 = getRoot(unionSet, string);
		String root2 = getRoot(unionSet, string2);
		unionSet.put(root2, root1);
	}

	private String getRoot(Map<String, String> unionSet, String string) {
		while (unionSet.get(string) != string) {
			string = unionSet.get(string);
		}
		return string;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] grid = { { 1, 0, 0, 1, 0, 1, 1, 0, 0, 0 }, { 1, 1, 0, 0, 1, 0, 0, 0, 1, 0 },
				{ 0, 1, 1, 0, 1, 0, 0, 0, 1, 0 }, { 1, 0, 0, 1, 1, 1, 1, 0, 0, 0 }, { 0, 0, 1, 1, 1, 0, 0, 0, 1, 0 },
				{ 1, 0, 1, 1, 0, 0, 0, 1, 1, 0 }, { 1, 0, 0, 0, 1, 0, 1, 1, 1, 0 }, { 1, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
				{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0, 1, 0, 0, 0 } };
		System.out.println(new ContainVirus().containVirus(grid));
	}

}
